In this paper, by constructing extremely hard examples of CSP (with large domains) and SAT (with long clauses), we prove that such examples cannot be solved without exhaustive search, which is stronger than P $\neq$ NP. This constructive approach for proving impossibility results is very different (and missing) from those currently used in computational complexity theory, but is similar to that used by Kurt G\"{o}del in proving his famous logical impossibility results. Just as shown by G\"{o}del's results that proving formal unprovability is feasible in mathematics, the results of this paper show that proving computational hardness is not hard in mathematics. Specifically, proving lower bounds for many problems, such as 3-SAT, can be challenging because these problems have various effective strategies available for avoiding exhaustive search. However, in cases of extremely hard examples, exhaustive search may be the only viable option, and proving its necessity becomes more straightforward. Consequently, it makes the separation between SAT (with long clauses) and 3-SAT much easier than that between 3-SAT and 2-SAT. Finally, the main results of this paper demonstrate that the fundamental difference between the syntax and the semantics revealed by G\"{o}del's results also exists in CSP and SAT.

In this work, we use large language models (LLMs) to augment and accelerate research on the P versus NP problem, one of the most important open problems in theoretical computer science and mathematics. Specifically, we propose Socratic reasoning, a general framework that promotes in-depth thinking with LLMs for complex problem-solving. Socratic reasoning encourages LLMs to recursively discover, solve, and integrate problems while facilitating self-evaluation and refinement. Our pilot study on the P vs. NP problem shows that GPT-4 successfully produces a proof schema and engages in rigorous reasoning throughout 97 dialogue turns, concluding "P $\neq$ NP", which is in alignment with (Xu and Zhou, 2023). The investigation uncovers novel insights within the extensive solution space of LLMs, shedding light on LLM for Science.

In many combinatorial optimization and decision problems, what people concern is to find solutions of minimal costs. In practice, however, such optimal solutions can be very brittle in that if the value of one variable becomes unavailable, repairing this solution leads to a great increase in its final cost. Therefore, the concept of super solution is introduced to formalize a solution with a certain degree of robustness or stability. To quantify the robustness, (a, b)-super solution was introduced to constraint programming in [3]. Specifically, an (a,b)-super solution is one in which if the values assigned to a variables are no longer available, the solution can be repaired by assigning these variables withanew values and at most b other variables. Over the past years, random models of constraint satisfaction problems (CSPs) have been intensively studied. Initially, four "standard" models known as models A, B, C and D [4, 2] have been introduced to generate random binary CSP instances.

The study of random constraint satisfaction problems (CSPs) has received tremendous ideas from combinatorics, computer science and statistical physics. Random CSPs contain a large set of variables which interact through a large set of constraints, where each variable ranges over a domain and a configuration (solution) to all the variables should satisfy all of the constraints. A fundamental question in the study of random CSPs is the average-case computational complexity of solving ensembles of CSPs. Great amount of theoretical and algorithmic work has been devoted to establish and locate the satisfiability threshold, and studies show that complexity attains the maximum at the SAT-UNSAT transition. Many of the studied CSP models (such as random k-SAT, graph coloring) have fixed domain size, constraint length, and the number of constraints is linear compared with the number of variables. In recent years, a lot of attention has been paid to the study of CSPs with growing domains or constraint length ([13, 7, 4, 5]).

The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.

The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.

This paper analyzes the scaling window of a random CSP model (i.e. model RB) for which we can identify the threshold points exactly, denoted by $r_{cr}$ or $p_{cr}$. For this model, we establish the scaling window $W(n,\delta)=(r_{-}(n,\delta), r_{+}(n,\delta))$ such that the probability of a random instance being satisfiable is greater than $1-\delta$ for $rr_{+}(n,\delta)$. Specifically, we obtain the following result $$W(n,\delta)=(r_{cr}-\Theta(\frac{1}{n^{1-\epsilon}\ln n}), \ r_{cr}+\Theta(\frac{1}{n\ln n})),$$ where $0\leq\epsilon<1$ is a constant. A similar result with respect to the other parameter $p$ is also obtained. Since the instances generated by model RB have been shown to be hard at the threshold, this is the first attempt, as far as we know, to analyze the scaling window of such a model with hard instances.